// https://leetcode.cn/problems/create-maximum-number/
// Created by ade on 2022/10/27.
// 给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
//
//求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> maxNumber1(vector<int> &nums1, vector<int> &nums2, int k) {
        // 这种方法不行   {3, 9} {8, 9} 无法回溯
        /*vector <pair<int, int >> st = {}; // 0-nums1 1-nums2
        int i = 0, j = 0;
        int len1 = nums1.size();
        int len2 = nums2.size();
        int left_count = len1 + len2; // 剩余可用的数 left_count + st.size() >= k
        // vector<int> nums1 = {3, 4, 6, 5};
        //    vector<int> nums2 = {9, 1, 2, 5, 8, 3};
        while (i < len1 || j < len2) {
            if (i < len1 && j < len2) {
                // 第1种情况
                cout << "i1:" << i << ",nums[i]:" << nums1[i] << ",j:" << j << ",nums[j]:" << nums2[j];
                if (nums1[i] >= nums2[j]) {
                    while (!st.empty() &&
                           st.back().second < nums1[i] &&
                           left_count + st.size() > k) {
                        if (st.back().first == 1) {
                            j--;
                            left_count++;
                        }
                        st.pop_back();
                    }

                    st.push_back({0, nums1[i]});
                    i++;
                    left_count--;
                } else {
                    while (!st.empty() &&
                           st.back().second < nums2[j] &&
                           left_count + st.size() > k) {
                        if (st.back().first == 0) {
                            i--;
                            left_count++;
                        }
                        st.pop_back();
                    }

                    st.push_back({1, nums2[j]});
                    j++;
                    left_count--;
                }
                cout << ",size:" << st.size() << ",back1:" << st.back().second << ",left_count:" << left_count << endl;
            } else if (i >= len1 && j < len2) {
                // 第2种情况
                while (!st.empty() &&
                       st.back().second < nums2[j] &&
                       (left_count + st.size() > k || left_count + st.size() == k && st.back().first == 0)
                        ) {
                    if (st.back().first == 0) {
                        i--;
                        left_count++;
                    }
                    st.pop_back();

                }
                st.push_back({1, nums2[j]});
                j++;
                left_count--;
                cout << "i2:" << i << ",nums[i]:" << nums1[i] << ",j:" << j << ",nums[j]:" << nums2[j] << ",size:" << st.size() << ",back:" << st.back().second
                     << ",left_count:" << left_count << endl;
            } else if (i < len1 && j >= len2) {
                // 第3种情况
                cout << "i3:" << i << ",nums[i]:" << nums1[i] << ",j:" << j << ",nums[j]:" << nums2[j]<< ",size:" << st.size() << ",back:" << st.back().second << endl;
                while (!st.empty() &&
                       st.back().second < nums1[i] &&
                       (left_count + st.size() > k || left_count + st.size() == k && st.back().first == 1)
                        ) {
                    if (st.back().first == 1) {
                        j--;
                        left_count++;
                    }
                    st.pop_back();
                }
                st.push_back({0, nums1[i]});
                i++;
                left_count--;
            } else {
                break;
            }
        }
        cout << st.size() << "i:" << i << ",j:" << j << endl;
        if (i < len1)
            for (; i < len1; i++)
                st.push_back({0, nums1[i]});

        if (j < len2)
            for (; j < len2; j++)
                st.push_back({1, nums2[j]});


        vector<int> res = {};
        for (int i = 0; i < st.size(); i++) {
            res.push_back(st[i].second);
        }
        return res;*/
        return {};
    }

    void show(vector<int> v) {
        for (auto &i:v) {
            cout << i << ",";
        }
        cout << endl;
    }

    vector<int> maxNumber(vector<int> &nums1, vector<int> &nums2, int k) {
        // 这种方法不行   {3, 9} {8, 9} 无法回溯
        vector<int> res(k, 0);
        int len1 = nums1.size();
        int len2 = nums2.size();
        // i 代表的是长度
        cout << min(k, len1) << endl;
        for (int i = 0; i <= min(k, len1); i++) {
            if (k - i > len2) continue;
            vector<int> t1 = maxArr(nums1, i);
            vector<int> t2 = maxArr(nums2, k - i);
            vector<int> tmp = merge(t1, t2);
            if (bigger(tmp, res)) res.assign(tmp.begin(), tmp.end());
        }

        for (int i = 0; i <= min(k, len2); i++) {
            if (k - i > len1) continue;
            vector<int> t1 = maxArr(nums2, i);
            vector<int> t2 = maxArr(nums1, k - i);
            vector<int> tmp = merge(t1, t2);
            if (bigger(tmp, res)) res.assign(tmp.begin(), tmp.end());
        }

        return res;
    }

    vector<int> maxArr(vector<int> &nums, int k) {
        vector<int> st = {};
        int left_count = nums.size();
        for (int i = 0; i < nums.size(); i++) {
            if (st.empty() || st.size() + left_count == k) {
                st.push_back(nums[i]);
                left_count--;
                continue;
            }
            while (!st.empty() && st.back() < nums[i] && st.size() + left_count > k) st.pop_back();
            st.push_back(nums[i]);
            left_count--;
        }
        while (st.size() > k) st.pop_back();
        return st;
    }

    vector<int> merge(vector<int> &v1, vector<int> &v2) {
        vector<int> res = {};
        int i = 0, j = 0;
        while (i < v1.size() && j < v2.size()) {
            if (v1[i] > v2[j]) {
                res.push_back(v1[i]);
                i++;
            } else if (v1[i] < v2[j]) {
                res.push_back(v2[j]);
                j++;
            } else {
                int k = 0;
                while (i + k < v1.size() && j + k < v2.size() && v1[i + k] == v2[j + k]) k++;
                if (i + k == v1.size()) {
                    for (int l = 0; l < k; l++) {
                        res.push_back(v1[i + l]);
                    }
                    i += k;
                } else if (j + k == v2.size()) {
                    for (int l = 0; l < k; l++) {
                        res.push_back(v2[j + l]);
                    }
                    j += k;
                } else if (i + k < v1.size() && j + k < v2.size() && v1[i + k] > v2[i + k]) {
                    for (int l = 0; l < k; l++) {
                        res.push_back(v1[i + l]);
                    }
                    i += k;
                } else {
                    for (int l = 0; l < k; l++) {
                        res.push_back(v2[j + l]);
                    }
                    j += k;
                }
            }
        }
        while (i < v1.size()) res.push_back(v1[i++]);
        while (j < v2.size()) res.push_back(v2[j++]);
        return res;
    }

    bool bigger(vector<int> &v1, vector<int> &v2) {
        int i = 0;
        while (i < v1.size()) {
            if (v1[i] > v2[i]) return true;
            if (v1[i] < v2[i]) return false;
            i++;
        }
        return false;
    }
};

int main() {
    Solution so;
    // [4,3,1,6,5,4,7,3,9,5,3,7,8,4, 1,3,5,9,1,1,4]
//    vector<int> nums1 = {1, 6, 5, 4, 7, 3, 9, 5, 3, 7, 8, 4, 1, 1, 4}; // 15
//    vector<int> nums2 = {4, 3, 1, 3, 5, 9}; // 6
//    so.show(so.merge(nums1, nums2));
//    return 0;[]
//[]
//9
    vector<int> nums1 = {7, 6, 1, 9, 3, 2, 3, 1, 1};
    vector<int> nums2 = {4, 0, 9, 9, 0, 5, 5, 4, 7};
    int k = 9;
    auto res = so.maxNumber(nums1, nums2, k);
    cout << endl;
    for (auto &i:res) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}
